#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2021-01-13 8:53 上午
# @Author  : yangdy
# @File    : 2021-01-13.684.冗余连接
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:

        class Union(list):
            def __init__(self, n):
                super().__init__()
                self._data = [i for i in range(n)]

            def _cut(self, x):
                if x != self._data[x]:
                    self._data[x] = self._cut(self._data[x])
                return self._data[x]

            def __getitem__(self, index):
                return self._cut(index)

            def union(self, x, y):
                self._data[self._cut(x)] = self._cut(y)

            def data(self):
                return self._data

        u = Union(len(edges) + 1)
        for ei in edges:
            if u[ei[0]] != u[ei[1]]:
                u.union(ei[0], ei[1])
            else:
                return [ei[0], ei[1]]
        return []

        # ss = [i for i in range(len(edges) + 1)]
        # def cut(x):
        #     if x != ss[x]:
        #         ss[x] = cut(ss[x])
        #     return ss[x]
        #
        # def union(x, y):
        #     ss[cut(x)] = cut(y)
        #
        # for ei in edges:
        #     if cut(ei[0]) != cut(ei[1]):
        #         union(ei[0], ei[1])
        #     else:
        #         return [ei[0], ei[1]]
        # return []


questions = [
    ([[1, 2], [1, 3], [2, 3]],),
    ([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]],),
]

work(questions, lambda q: Solution().findRedundantConnection(q[0]))
